package recursion;

/**
 * Given quarters, dimes, nickles, pennies to present N cents 
 * 
 * @author Lei
 */
public class GetNumberofWaysRepresentingNCents {

    public static int getNumberofWaysRepresentingNCents(int n, int denom) {
        int next_denom = 0;
        switch (denom) {
            case 25:
                next_denom = 10;
                break;
            case 10:
                next_denom = 5;
                break;
            case 5:
                next_denom = 1;
                break;
            case 1:
                return 1;
        }

        int ways = 0;
        for (int i = 0; i * denom <= n; i++) {
            ways += getNumberofWaysRepresentingNCents(n - i * denom, next_denom);

        }

        return ways;
    }

    public static void main(String[] args) {
        
        System.out.println(GetNumberofWaysRepresentingNCents.getNumberofWaysRepresentingNCents(7, 25));
    }
}
